package Sort._56_MergeIntervals;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class _56_MergeInterval {
    public List<Interval> merge(List<Interval> intervals) {
        List<Interval> res = new ArrayList<>();
        if (intervals == null || intervals.size() == 0) {
            return res;
        }
        //comparator
        Collections.sort(intervals, (a, b) -> a.start - b.start != 0 ? a.start - b.start : a.end - b.end);
        Interval temp = new Interval(intervals.get(0).start,intervals.get(0).end);
        for (int i = 1; i < intervals.size(); i++) {
            Interval ti = intervals.get(i);
            if (temp.start <= ti.start && ti.start <= temp.end) {
                if (temp.end < ti.end) {
                    temp.end = ti.end;
                }
            } else {
                res.add(temp);
                temp = ti;
            }
        }
        // the last interval
        res.add(temp);
        return res;
    }

}
